package 代码随想录_动态规划.子序列问题.编辑距离;

/**
 * @author zx
 * @create 2022-06-06 14:34
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               dp[i][j]：以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数.
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * (1)当word1[i - 1] 与 word2[j - 1]相同的时候
 * (2)当word1[i - 1] 与 word2[j - 1]不相同的时候
 *   当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
 *   当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
 *      A.情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
 *      B.情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
 *      C.情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
 * 那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候:
 * 递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
 * 组成部分三：初始条件和边界情况
 * 从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的.
 * dp[i][0]：word2为空字符串,以i-1为结尾的字符串word2要删除多少个元素,才能和word1相同呢,很明显dp[i][0] = i.
 * dp[0][j]的话同理
 * 组成部分四：计算顺序
 */
public class 两个字符串的删除操作_583 {
    /**
     从递推公式中可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的
     dp[i][0]：word2为空字符串,以i-1为结尾的字符串word2要删除多少个元素,才能和word1相同呢
     很明显dp[i][0] = i; dp[0][j]的话同理

     当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];
     当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况(最后取最小值)：
     情况一：删word1[i - 1],最少操作次数为dp[i - 1][j] + 1
     情况二：删word2[j - 1],最少操作次数为dp[i][j - 1] + 1
     情况三：同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2
     */
    public int minDistance(String word1, String word2) {
        //dp[i][j]：以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等
        //所需要删除元素的最少次数
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0; i <= word1.length(); i++) dp[i][0] = i;
        for(int j = 0; j <= word2.length(); j++) dp[0][j] = j;
        for(int i = 1;i <= word1.length();i++){
            for(int j = 1;j <= word2.length();j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
                            Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }



    /**
     * @return 最长公共子序列
     * 不看这个
     */
    public int minDistance2(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 1;i <= word1.length();i++){
            for(int j = 1;j <= word2.length();j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        int res = dp[word1.length()][word2.length()];
        return word1.length() - res + word2.length() - res;
    }
}
